package interview;

import java.util.HashMap;

public class interview_04_12 {
    public int pathSum(TreeNode root, int sum) {
        int[] result=new int[1];
        HashMap<Integer, Integer> hashMap=new HashMap<>();
        hashMap.put(0,1);
        path(hashMap,root,sum,result,0);
        return result[0];
    }
    public void path(HashMap<Integer, Integer> hashMap,TreeNode node,int sum,int[] result,int current){
        if(node==null) return;
        if(hashMap.containsKey(current-sum+node.val)){
            result[0]+=hashMap.get(current-sum+node.val);
        }
        if(hashMap.containsKey(current+node.val)){
            hashMap.put(current+node.val,hashMap.get(current+node.val)+1);
        }else{
            hashMap.put(current+node.val,1);
        }
        path(hashMap,node.left,sum,result,current+node.val);
        path(hashMap, node.right, sum, result, current+node.val);
        hashMap.put(current+node.val,hashMap.get(current+node.val)-1);
    }
}
